package com.zx._12_算法.剑指offer._2022;

/**
 * https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/第一个只出现一次的字符
 */
public class 连续子数组的最大和 {

    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int step = 1;// [1, nums.length]
        int max = -999999999;

        while (step <= nums.length) {
            for (int i = 0; i < nums.length - step + 1; i++) {
                int sum = 0;
                for (int j = i; j < i + step && j < nums.length; j++) {
                    sum += nums[j];
                }
                if (sum > max) {
                    max = sum;
                }
            }
            step++;
        }
        return max;
    }

    public int maxSubArray2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] res = new int[nums.length];
        int max = nums[0];
        res[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res[i] = Math.max(res[i - 1] + nums[i], nums[i]);
            max = Math.max(max, res[i]);
        }
        return max;
    }
}
